package demo1;

public class MySingleList implements IList {

    public static class ListNode{
        public int val;
       public  ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

    private int count;
    ListNode hear;
    public boolean chkPalindrome(ListNode A) {
       
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int len1 = size(headA);
        int len2 = size(headB);
        if(len1 > len2){
            for(int i = 0 ; i < len1-len2;i++){
                headA= headA.next;
            }
        }else {
            for(int i = 0 ; i < len2 - len1; i++){
                headB = headB.next;
            }
        }
        while(headA != null){
            if(headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return null;
    }
    public int size(ListNode head1){
        ListNode cur = head1;
        int count = 0;
        while(cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }
    public boolean hasCycle(ListNode head) {
     ListNode cur = head;
     ListNode curN = head;
     while(curN != null && curN.next != null){
         cur = cur.next;
         curN = curN.next.next;
         if(cur == curN){
             return true;
         }
     }
     return false;
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node1 = new ListNode(-1);
        ListNode head1 = node1;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                head1.next = list1;
                list1 = list1.next;
            }else {
                head1.next = list2;
                list2 = list2.next;
            }
            head1 = head1.next;
        }
        if(list1 == null){
            head1.next = list2;
        }
        if(list2 == null){
            head1.next = list1;
        }
        return node1.next;
    }
    public boolean hasCycle(ListNode head) {
        ListNode head1 = head;
        ListNode head2 = head;
        if(head == null || head.next == null){
            return false;
        }
        while(head2 != null && head2.next != null){
            head1 = head1.next;
            head2 = head2.next.next;
            if(head1 == head2){
                return true;
            }
        }
        return false;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode head1 = headA;
        ListNode head2 = headB;
        int len1 = nodeLen(headA);
        int len2 = nodeLen(headB);
        if(len1 > len2){
            for(int i = 0 ; i < len1 - len2; i++){
                head1 = head1.next;
            }
            while(head1 != null){
                if(head1 == head2){
                    return head1;
                }
                head1 = head1.next;
                head2 = head2.next;
            }
        }else {
            for(int i = 0 ; i < len2 - len1; i++){
                head2 = head2.next;
            }
            while(head2 != null){
                if(head1 == head2){
                    return head2;
                }
                head1 = head1.next;
                head2 = head2.next;
            }
        }
        return null;
    }
    public int nodeLen(ListNode head1){
        int count = 0;
        while(head1 != null){
            head1 = head1.next;
            count++;
        }
        return count;
    }
    public boolean chkPalindrome(ListNode A) {
        ListNode head1 = A;
        ListNode head2 = A;
        while(head2 != null && head2.next != null){
            head2 = head2.next.next;
            head1 = head1.next;

        }
        head2 = head1.next;
        head2 = reverseOrder(head2);
        return continues(head2,A);
    }

        public boolean chkPalindrome1(ListNode A) {
      ListNode head1 = A;
      ListNode head2 = A;

      while(head2 != null && head2.next != null ){

            head2 = head2.next.next;
          if(head2 != null && head2.next != null ){
              break;
          }
            head1 = head1.next;
      }
      head2 = head1.next;
      head1.next = null;
      head2 = reverseOrder(head2);
      if(continues(A,head2)){
          return true;
      }
       return false;
    }
    public boolean continues(ListNode A,ListNode head2){
        while(A != null){
            if(A.val != head2.val){
                return false;
            }
            A = A.next;
            head2 = head2.next;
        }
        return true;
    }
    public ListNode reverseOrder(ListNode head){
        ListNode cur = head.next;
        head.next = null;
        while(cur.next != null){
            ListNode pear = cur.next;
            cur.next = head;
            head = cur;
            cur = pear;
        }
        cur.next = head;
        head = cur;
        return head;
    }
    public ListNode partition(ListNode pHead, int x) {

       ListNode listNode1 = new ListNode(1);
       ListNode head1 = listNode1;
       ListNode listNode2 = new ListNode(1);
       ListNode head2 = listNode2;
        while (pHead != null) {
            if (pHead.val < x) {
                head1.next = pHead;
                head1 = head1.next;
            } else {
                head2.next = pHead;
                head2 = head2.next;

            }
            pHead = pHead.next;
        }
        head2.next = null;
        head1.next = listNode2.next;
        return listNode1.next;
    }
    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = this.hear;
        this.hear = node;
        count++;
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(this.hear == null){
            this.hear = node;
            return;
        }
        ListNode last = findLast(this.hear);
        last.next = node;
        count++;
    }
    private ListNode findLast(ListNode hear) {
        while (hear.next != null) {
            hear = hear.next;
        }
        return hear;
    }
    @Override
    public void addIndex(int index, int data) {
        if(index < 0 || index > this.count){
            return;
        }
        if(index == 0){
            addFirst(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = hear;
        for(int i = 0 ; i < index ; i++){
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
        count++;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = hear;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    @Override
    public void remove(int key){
        ListNode cur = this.hear;
        if(hear == null){
            return;
        }
        if(hear.val == key){
            hear = hear.next;
            return;
        }
        ListNode pear = cur.next;
        while(pear != null){
            pear = cur.next;
            if(pear.val == key){
                pear = pear.next;
                cur.next = pear;
                return;
            }
            cur = pear;
        }
    }

    public void remove1(int key) {
        ListNode cur = hear;
        for(int i = 1; i < findKey(key); i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        this.count--;
    }
    private int findKey(int key){
        ListNode cur  = this.hear;
        int count = 0;
        while(cur != null){

            if(cur.val == key){
                return count;
            }
            count++;
        }
        return -1;
    }

    @Override
    public void removeAllKey(int key) {
        if(hear == null){
            return;
        }
        ListNode cur = this.hear;
        while(cur.next != null){
            ListNode pear = cur.next;
            if(pear.val == key) {
                cur.next = pear.next;
            }else {
                cur = cur.next;
            }
        }
        if(hear.val == key){
            this.hear = hear.next;
        }
    }

    @Override
    public int size() {
        return this.count;
    }

    @Override
    public void clear() {
        this.hear = null;
        this.count = 0;
    }

    @Override
    public void display() {
        ListNode cur = this.hear;
     while(cur != null){
          System.out.print(cur.val + " ");
          cur = cur.next;
      }
        System.out.println();
    }
    public void display(ListNode hear) {
        ListNode cur = hear;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }
}
